package 回溯;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/2/1 10:42
 */
public class leetcode139单词拆分2023 {
    /*
    重新来写 这个 题
    这个 测试  用例 会 wa 一下
    "aaaaaaa"
    ["aaaa","aaa"]
     */

    public boolean solution(String s, List<String> dict){
         Set<String> map = new HashSet<>();
         for(String str : dict){
             map.add(str);
         }
         // 0 表示 未 计算， 1 ： true  2 ： false
         int flag[] = new int[s.length()];
         return recursion(0,s,map,flag);
    }

    public boolean recursion(int index,String s,Set<String> map,int flag[]){
        if(index == s.length()){
            return true;
        }
        if(flag[index] != 0){
            return flag[index] == 1;
        }

        for(int i = index + 1;i <= s.length();i++) {
            if (map.contains(s.substring(index, i)) && recursion(i,s,map,flag)) {
//                return recursion(i, s, map);
                return true;
            }
        }
        flag[index] = 2;
        return false;
    }





}
